package com.xcc.dataStructures.demo06_algorithm;

/**
 * 希尔排序
 *
 * @author xiaocheng
 * @date 2020/12/3 15:08
 */
public class ShellSort {

    public static void main(String[] args) {
//        int[] arr = {32, 7, 12, 11, 90, 5, 1};
        int data = 1500000;//15w数据
        int[] arr = new int[data];
        for (int i = 0; i < data; i++) {
            arr[i] = (int) (Math.random() * data);
        }
        long startTime = System.currentTimeMillis();
        shellSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("时长：" + ((endTime - startTime) ));
//        System.out.println(Arrays.toString(arr));
    }


    public static void shellSort(int[] arr) {
        if (arr == null) {
            return;
        }
        //gap表示步长，每次都会缩短步长
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                //添加while循环，当移动完成之后(11...32...1) => (11...1...32)接着与前一个进行比较 => (1...11...32)
                while (j - gap >= 0 && arr[j] < arr[j-gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                //如果发现两个值不相等 前面判断已经交换过了  此时将temp值赋给arr[j]
                if (temp != arr[j]) {
                    arr[j] = temp;
                }
            }
        }
    }

}
